package demo9;

import java.util.Arrays;
import java.util.Scanner;

/**
 * 完全背包问题
 */
public class test1 {
    public static void main(String[] args) {
        // 创建dp表
        int N = 1010;
        int n = 0,V = 0;
        int[] v = new int[N];
        int[] w = new int[N];
        int[][] dp = new int[N][N];

        // 输入数据
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        V = sc.nextInt();
        for(int i = 1;i<=n;i++){
            v[i] = sc.nextInt();
            w[i] = sc.nextInt();
        }

        // 第一问：不一定装满
        // 初始化 无需初始化
        // 填表
        for(int i = 1;i<=n;i++){
            for(int j = 0;j<=V;j++){
                dp[i][j] = dp[i-1][j];
                if(j >= v[i]){
                    dp[i][j] = Math.max(dp[i][j], dp[i][j-v[i]]+w[i]);
                }
            }
        }
        System.out.println(dp[n][V]);

        // 重置dp表
        for(int i = 0;i< dp.length;i++){
            Arrays.fill(dp[n],0);
        }

        // 第二问：必须装满
        // 初始化
        for(int j =1;j<=V;j++){
            dp[0][j] = -1;
        }
        // 填表
        for(int i = 1;i<=n;i++){
            for(int j = 0;j<=V;j++){
                dp[i][j] = dp[i-1][j];
                if(j >= v[i] && dp[i][j-v[i]] != -1){
                    dp[i][j] = Math.max(dp[i][j], dp[i][j-v[i]]+w[i]);
                }
            }
        }
        System.out.println(dp[n][V] == -1?0:dp[n][V]);
    }
}
